//<p>给定一个按照升序排列的整数数组 <code>nums</code>，和一个目标值 <code>target</code>。找出给定目标值在数组中的开始位置和结束位置。</p>
//
//<p>如果数组中不存在目标值 <code>target</code>，返回 <code>[-1, -1]</code>。</p>
//
//<p><strong>进阶：</strong></p>
//
//<ul>
//	<li>你可以设计并实现时间复杂度为 <code>O(log n)</code> 的算法解决此问题吗？</li>
//</ul>
//
//<p> </p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [<code>5,7,7,8,8,10]</code>, target = 8
//<strong>输出：</strong>[3,4]</pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [<code>5,7,7,8,8,10]</code>, target = 6
//<strong>输出：</strong>[-1,-1]</pre>
//
//<p><strong>示例 3：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [], target = 0
//<strong>输出：</strong>[-1,-1]</pre>
//
//<p> </p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>0 <= nums.length <= 10<sup>5</sup></code></li>
//	<li><code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code></li>
//	<li><code>nums</code> 是一个非递减数组</li>
//	<li><code>-10<sup>9</sup> <= target <= 10<sup>9</sup></code></li>
//</ul>
//<div><div>Related Topics</div><div><li>数组</li><li>二分查找</li></div></div><br><div><li>👍 1674</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

/**
 * 在排序数组中查找元素的第一个和最后一个位置
 * @author DY Rising
 * @date 2022-05-11 16:08:43
 */
public class P34_FindFirstAndLastPositionOfElementInSortedArray{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P34_FindFirstAndLastPositionOfElementInSortedArray().new Solution();
        solution.searchRange(new int[]{1,2,2}, 2);
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] rtns = new int[] {-1, -1};
        if (nums.length == 0) return rtns;
        if (nums.length == 1 && nums[0] == target) {
            rtns[0] = 0; rtns[1] = 0;
            return rtns;
        }
        twoSplit(nums, 0, nums.length - 1, rtns, target);
        return rtns;
    }

    public void twoSplit(int[] nums, int leftIndex, int rightIndex, int[] rtns, int target) {
        if (leftIndex >= rightIndex) return;
        if (nums[leftIndex] == target) {
            setRtns(rtns, leftIndex);
        }
        if (nums[rightIndex] == target) {
            setRtns(rtns, rightIndex);
        }

        int mid = (leftIndex + rightIndex) >> 1;
        twoSplit(nums, leftIndex, mid, rtns, target);
        twoSplit(nums, mid + 1, rightIndex, rtns, target);
    }

    public void setRtns(int[] rtns, int index) {
        if (rtns[0] == -1) rtns[0] = index;
        else rtns[0] = Math.min(rtns[0], index);
        if (rtns[1] == -1) rtns[1] = index;
        else rtns[1] = Math.max(rtns[1], index);
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
